/*
https://leetcode.cn/problems/remove-boxes/description/?envType=problem-list-v2&envId=AnEpLQwV
546. 移除盒子
*/

class Solution {
public:
    int dp[100][100][100];

int test(vector<int>& boxes, int l, int r, int k) {
        if (l > r) {  //如果l>r,不符合我们的序列的定义,直接返回0
            return 0;
        }
        if (dp[l][r][k] == 0) {  //(记忆化)如果当前序列的值为0
            dp[l][r][k]=test(boxes,l,r-1,0)+(k+1)*(k+1);//计算当前序列的最优结果
            for (int i = l; i < r; i++) { //进行遍历,对每个序列进行判断,求出最大值
                if (boxes[i] == boxes[r]) {  //如果序列内存在i==r的,进行求解2种情况的最大值
                   dp[l][r][k]=max(dp[l][r][k],test(boxes,l,i,k+1)+test(boxes,i+1,r - 1,0));  //求出当前序列的最大积分和
                }
            }
        }
        return dp[l][r][k];//返回当前序列的最大积分和
    }

    int removeBoxes(vector<int>& boxes) {
        memset(dp, 0, sizeof dp);  //初始化数组
        return test(boxes, 0, boxes.size() - 1, 0);  //调用函数返回最优结果
    }
};
//[2,4,3,2,2,2]

//dp[l][r][k]=test(boxes,l,r-1,0)+(k+1)*(k+1)
//计算[0~6] [0~5] [0~4] [0~3] [0~2] [0~1] [0~0] [0~-1]结束

//     if (boxes[i] == boxes[r])
//     dp[l][r][k]=max(dp[l][r][k],test(boxes,l,i,k+1)+test(boxes,i+1,r - 1,0));
//计算区间[0~1] [0~2] [1~2] [0~3] [1~3] [2~3] [0~4] [1~4] [2~4] [3~4]........如果存在相同的if(boxes[i] == boxes[r])

//判断到[0,3] 此时2==2 那判断在这个区间内，是一个一个取好，还是先取[4,3]再取[2,2]好(此时传参0,0,1) 1表示[0,3]范围内在[0,0]后面还存在一个2
//判断到[0,4] 此时2==2 那判断在这个区间内，是一个一个取好，还是先取[4,3,2]再取[2,2]好(此时传参0,0,1) 1表示[0,4]范围在[0,0]后面还存在一个2
//判断到[3,4] 此时2==2 那判断在这个区间内，是一个一个取好，还是先取[]再取[2,4,3,2,2]好(此时传参0,3,1) 1表示[3,4]范围在[0,3]后面还存在一个2
//接着计算[0,3]区间,同时k==1,如果[0,3]区间中存在下标i和r值相同即存在2,此时在区间[0,4]内已知存在3个2.然后又缩小范围
//比如[0,3]范围内在下标1，2处还存在2  [1,2,2,2,2]
//此时我们先算[1,3]处的，此时就是[0,1](传参0,1,2) 2表示[0,4]范围在[0,1]后面还存在2个2 然后没有了
//算[2,3]处的，此时就是[0,2](传参0,2,2) 2表示[0,4]范围在[0,2]后面还存在2个2
//此时范围[0,2]内,发现下标1处还存在1,此时[0,1](传参0，1，3) 3表示[0,1]范围在[0,1]后面还存在3个2
//然后分别算[0,1]==1返回即可




